//Given the head of a singly linked list, group all the nodes with odd indices t
//ogether followed by the nodes with even indices, and return the reordered list. 
//
//
// The first node is considered odd, and the second node is even, and so on. 
//
// Note that the relative order inside both the even and odd groups should remai
//n as it was in the input. 
//
// You must solve the problem in O(1) extra space complexity and O(n) time compl
//exity. 
//
// 
// Example 1: 
//
// 
//Input: head = [1,2,3,4,5]
//Output: [1,3,5,2,4]
// 
//
// Example 2: 
//
// 
//Input: head = [2,1,3,5,6,4,7]
//Output: [2,3,6,7,1,5,4]
// 
//
// 
// Constraints: 
//
// 
// n == number of nodes in the linked list 
// 0 <= n <= 104 
// -106 <= Node.val <= 106 
// 
// Related Topics 链表 
// 👍 524 👎 0


package leetcode.editor.cn;

//Java：Odd Even Linked List
public class P328OddEvenLinkedList {
    public static void main(String[] args) {
        Solution solution = new P328OddEvenLinkedList().new Solution();
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
//        listNode4.next = listNode5;
        ListNode temp = solution.oddEvenList(listNode1);
        System.out.println(temp);
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode oddEvenList(ListNode head) {
            ListNode odd = new ListNode(-1);
            ListNode oddNext = odd;
            ListNode even = new ListNode(-1);
            ListNode evenNext = even;
            ListNode cur = head;
            while (cur != null) {
                if (oddNext != null) {
                    oddNext.next = cur;
                }
                if (evenNext != null) {
                    evenNext.next = cur.next;
                }
                cur = evenNext.next;
                if (evenNext.next != null) {
                    cur = cur.next;
                    evenNext.next.next = null;
                }
                oddNext = oddNext.next;
                evenNext = evenNext.next;
            }
            odd = odd.next;
            even = even.next;
            oddNext.next = even;
            return odd;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}